Năm 1907, hội đồng thành phố quyết định xây dựng một tòa thị chính mới tại địa điểm cũ của Eldkvarn. Một cuộc thi kiến ​​trúc đã được tổ chức trong giai đoạn đầu tiên dẫn đến việc lựa chọn các bản nháp của Ragnar stberg, Carl Westman, Ivar Tengbom cùng với Ernst Torulf và Carl Bergsten. Sau một cuộc cạnh tranh tiếp theo giữa Westman và Östberg, người thứ hai được giao nhiệm vụ xây dựng Tòa thị chính, trong khi trước đây được yêu cầu xây dựng Tòa án Stockholm. Östberg đã sửa đổi dự thảo ban đầu của mình bằng các yếu tố của dự án Westman, bao gồm cả tòa tháp. Trong thời gian xây dựng, Bergstberg liên tục làm lại các bản vẽ của mình, dẫn đến việc bổ sung đèn lồng trên đỉnh tháp và từ bỏ các viên gạch tráng men màu xanh cho Hội trường xanh.

Oskar Asker được thuê làm lãnh đạo xây dựng và Paul Toll, của công ty xây dựng Kreuger & Toll, đã thiết kế nền móng. Georg Greve cũng hỗ trợ chuẩn bị các bản vẽ quy hoạch.[3] Việc xây dựng mất mười hai năm, từ 1911 đến 1923. Gần tám triệu viên gạch màu đỏ đã được sử dụng. Những viên gạch màu đỏ sẫm, được gọi là "munktegel" (gạch của nhà sư) vì sử dụng truyền thống trong việc xây dựng các tu viện và nhà thờ, được cung cấp bởi nhà máy gạch Lina gần Södertälje. Xây dựng được thực hiện bởi các thợ thủ công sử dụng các kỹ thuật truyền thống.

Tòa nhà được khánh thành vào ngày 23 tháng 6 năm 1923, chính xác 400 năm sau khi Gustav Vasa đến Stockholm. Verner von Heidenstam và Hjalmar Branting đã có bài phát biểu khai mạc.